package sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @author shkstart
 * 七大排序的实现
 * @create 2022-11-06-21:49
 */
public class SevenSort {
    private static final ThreadLocalRandom random =ThreadLocalRandom.current();

    //    直接选择排序
    public static void selectionSort(int[] arr) {
    /*
    每次从待排序数组中选择最小值放在待排序数组的最前面、
    最外层的for循环要执行的总次数类似于冒泡排序，当剩下最后一趟时，整个数组已经有序
    默认第一个元素是有序的
    已经有序的元素集合[0,j)
    待排序的集合[i+1，n)
    每进行依次排序，最小值就放在了数组的最前面，已经有序的集合元素个数+1
    待排序的元素个数-1
     */
        for (int i = 0; i < arr.length - 1; i++) {
            //min变量存储了最小值元素的下标
            int min = i;
            //每次从无序区间中选择最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            swap(arr, i, min);

        }
    }

    //    双向选择排序  每次选出最小值放前面，最大值放后面
    public static void selectionSortOP(int[] arr) {

        int low = 0;
        int high = arr.length - 1;
        //有序区间[0,low+1)
        while (low < high) {
            int min = low;
            int max = low;
            for (int j = low + 1; j <= high; j++) {
                if (arr[j] > arr[max]) {
                    max = j;
                }
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
//            min存储了无序区间的最小值，max存储了无序区间的最大值
            swap(arr, low, min);
            if (max == low) {
                max = min;
            }
            swap(arr, max, high);
            low += 1;
            high -= 1;

        }


    }

    //    直接插入排序
    public static void insertionSortBase(int[] arr) {
        //有序区间[0,i)   [0,1)
//        默认第一个元素是有序
        for (int i = 0; i < arr.length; i++) {
            //每次都从无序区间选择第一个元素插入到有序区间的合适位置
//            无序区间[i,n)
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
//            for (int j = i; j >0 ; j--) {
//                if(arr[j]<arr[j-1]){
//                    swap(arr,j,j-1);
//                }else{
//                    //arr[j]>=arr[l-1] 小数在前，大数在后 位置正确
//                    break;
//                }
//            }
        }


    }

    //    折半直接查找
    public static void insertionSortBS(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //无序区间第一个值
            int val = arr[i];
//            有序区间[0,i)
            int low = 0;
            int high = i;
            while (low < high) {
                int mid = (low + high) >> 1;
                if (val >= arr[mid]) {
                    low = mid + 1;
                } else {
                    //右区间取不到，不用-1；
                    high = mid;
                }
            }
            //数据搬移
            for (int j = i; j > low; j--) {
                arr[j] = arr[j - 1];
            }
//            此时Low就是元素的插入位置
            arr[low] = val;

        }
    }

//    希尔排序
    public static void shellSort(int[] arr){
        int gap = arr.length>>1;
        while(gap>1){
            //不断按照gap分组，组内进行插入排序
            insertionSortGap(arr,gap);
            gap/=2;
        }
        //对整个数组进行插入排序
        insertionSortGap(arr,1);
    }

    //在arr上进行归并排序
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length-1);
    }
//
    private static void mergeSortInternal(int[] arr, int l, int r) {
        if(r-l<=15){
//            拆分后的小区间直接使用插入排序，不在递归
            insertBase(arr,l,r);
            return ;
        }
//        if(l>=r){
//            return ;
//        }

//        直接将Mid计算为(r+l)/2 有溢出的风险
        int mid = l +((r-l)>>1);

//        在拆分后的两个小数组上使用归并排序
//        先排序左半区
        mergeSortInternal(arr,l,mid);
//        再排序右半曲
        mergeSortInternal(arr,mid+1,r);

        //此时左右半区已经有序
//        arr[mid]是左区间的最后一个元素
//        arr[mid+1]是右区间的第一个元素
//        如果arr[mid]<arr[mid+1]成立，则此时整个数组已经有序，不需要merge
//        不需要直接merge，而是先判断左右半区数组交界的大小
        if(arr[mid]>arr[mid+1]){
        merge(arr, l, mid, r);
        }

    }
    //非递归版本的归并排序
    public static void mergeSortNonRecursion(int[]arr){
 /*sz表示每次合并的元素个数，最开始从1个元素开始合并（每个数组只有一个元素）
                      第二次合并时，合并的元素有2个
                      第三次合并时，合并的元素有4个
                      第四次合并时，合并的元素有8个

 */
        for (int sz = 1; sz <= arr.length; sz= sz+sz) {
//            merge过程，i表示每次merger的开始索引下标
            for (int i = 0; i+sz < arr.length; i+= sz + sz) {
//                i+sz,表示第二个小数组的开始索引 <n表示还有右半区间有合并
//            当sz长度过大时,i+2sz-1会超过数组长度
                merge(arr, i, i + sz - 1, Math.min(i + 2 * sz - 1, arr.length - 1));
            }

        }



    }




//将已经有序的arr[l,mid] 和  [mid+1,r]合并成为一个大的有序数组
    private static void merge(int[] arr, int l, int mid, int r) {
//    假设此时l=1000,r=2000
//    开辟一个大小和 合并之后数组大小相同数组
     int[]temp = new int[r-l+1];
//     将原数组内容拷贝到数组中
        for (int i = l; i <=r ; i++) {
//        temp[0] = arr[1000]
//        新数组的索引和原数组的索引有l个单位的偏移量
          temp[i-l] = arr[i];
        }

//      遍历原数组， 选择左半区间和右半区间的最小值写回原数组
//     i对应左半1间的第一个索引
        int i =l;
//        j对应右半区间的第一个索引
        int j = mid+1;
//      k表示当前处理到原数组的哪个位置
        for (int k = l; k <=r ; k++) {
            if(i> mid){
//                此时左半区间已经处理完毕,直接将右半区剩余的所有值写回原数组
                arr[k] = temp[j-l];
                j++;
            }else if(j>r){
//                此时右半区处理完毕
                arr[k]= temp[i-l];
                i++;
            }else if(temp[i-l]<= temp[j-l]){
                arr[k] = temp[i-l];
                i++;
            }else{
                arr[k] = temp[j-l];
                j++;
            }
        }
    }


    private static void insertionSortGap(int[] arr, int gap) {
        //最外层从gap开始不断走到数组末尾
        for (int i = gap; i <arr.length ; i++) {
            //最内层从gap索引向前看（至少保证有一组数据），看到元素就是距离她gap长度的元素
            //不断比较当前元素和前gap个元素的大小
//            j-gap>=0说明前面的数组还要比较相同距离的元素，比较arr[j]和arr[j-gap]
            for (int j = i; j -gap>=0&&arr[j]<arr[j-gap] ; j=j-gap) {
                swap(arr,j,j-gap);
            }
        }
        
    }



    //    将任意数组进行原地堆排序
    public static void heapSort(int [] arr){
//        1.将任意数组调整为最大堆
//        从最后一个非叶子节点开始
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            siftDown(arr,i,arr.length-1);
        }
//        依次将堆顶元素和最后位置元素交换
//        最开始待排序数组[0..arr.length - 1]  已排序的数组[null]
//        交换一个后 待排序[0....arr.length-2]   已排序[arr.length-1]
//        交换两个后 待排序[0....arr.length-3]   已排序[arr.length-2，arr.length-1]
//        终止条件不写i= 0,当整个待排序数组就剩一个元素时，整个数组已经有序
        for(int i  = arr.length-1;i>0;i--){
            swap(arr, 0,i);
            siftDown(arr,0,i);
        }



    }

    /*
    冒泡排序
     */
    public static void bubbleSort(int[]arr){
//        最外层表示要比较的次数，此处-1是因为整个待排序数组剩下一个元素时，整个数组已经有序
        for (int i = 0; i < arr.length-1; i++) {

            boolean isSwaped = false;
            for (int j = 0; j <arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    isSwaped =true;
                    swap(arr,j,j+1);
                }
            }
            if(!isSwaped){
//                内层循环没有元素的交换，整个数组有序
                break;
            }
        }
    }

//    在arr[l...r]使用插入排序
    private static void insertBase(int[] arr,int l ,int r){
//        有序区间[L i）
//        无序区间[i，r]
        for (int i = l+1; i <=r; i++) {
            for (int j = i; j >l&&arr[j]<arr[j-1] ; j--) {
                swap(arr,j,j-1);

            }

        }


    }




    /*
    元素下沉
    n当前arr中有效的元素个数

     */
    private static void siftDown(int[] arr, int i, int n) {
//        任然有子树
        while((2*i)+1<n){
            int j = 2*i +1;
//            右子树存在并且大于左子树的值
            if(j+1<n && arr[j+1]>arr[j]){
//                左子树j替换了右子树j+1
                j=j+1;
            }
//            此时的J是左右子树中值最大的索引下标
            if(arr[i]>=arr[j]){
                break;
            }else {
//                需要下沉
                swap(arr, i, j);
                i = j;
            }

        }

    }


    //基础快速排序
    public static void quickSort(int[]arr){
        quickSortInternal(arr,0,arr.length-1);
    }


    //在l..r上快速排序
    private static void quickSortInternal(int[] arr, int l, int r) {

        //递归终止时，小数组使用插入排序
        if (r - l <= 15) {
            insertBase(arr,l,r);
            return ;
        }

//        选择基准值，找到该值对应的下标
        int p = partition(arr,l,r);
//        在小区间进行快速排序
        quickSortInternal(arr,l,p-1);
//        在>=区间进行快速排序“
        quickSortInternal(arr,p+1,r);

    }

    /*
    在arr[l...r]上选择基准值，将数组划分为<v 和 >= v 两部分，返回基准值的索引下标
     */
    private static int partition(int[] arr, int l, int r) {
//      在当前数组中随机选取一个元素作为基准值
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v= arr[l];
        //arr[l+1...j] < v
        int j = l;
        //i是当前处理元素的下标
        //arr[l+1...j] < v 最开始为空区间 [l+1 .. l]= 0
        //arr[j+1...i] >= v 最开始为空区间 [l+1 .. l+1]= 0
        for (int i = l+1; i <= r ; i++) {
            if(arr[i] < v){
                swap(arr,j+1,i);
//                小于v的元素值新增一个
                j++;
            }


        }
// 此时j下标对应的就是最后一个 < V 的元素，交换j 和 l的值，选取的基准值交换 j 的位置
        swap(arr,l,j);
        return j;
    }

//    双路快排
    public static void quickSort2(int[] arr){
        quickSortInternal2(arr,0,arr.length-1);
    }

    private static void quickSortInternal2(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertBase(arr,l,r);
            return ;
        }
        int p = partition2(arr,l,r);
        quickSortInternal2(arr,l,p-1);
        quickSortInternal2(arr,p+1,r);




    }

    private static int partition2(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v= arr[l];
//        arr[l+1,,,,,i ) < v
        int i = l+1;//为了使开始时的数组为空
//        arr ([) j,,,,r ] > v
        int j = r;
        while(true){
            //i从前向前后描碰到第一个 >= v 的元素停止
            while (i<=r && arr[i]< v){
                i++;
            }
            //j从后向前扫描碰到第一个 >= v 的元素停止
            while (j>=l+1 && arr[j]> v){
                j--;
            }
            if(i>j){
//                此时整个数组已经扫描完毕
                break;
            }
            swap(arr,i,j);
            i++;j--;

        }
//        此时j 落在左后一个<= v 的元素
        swap(arr,l,j);
        return j;
    }

    public static void quickSort3(int[] arr){
        quickSortInternal3(arr,0,arr.length-1);
    }

    private static void quickSortInternal3(int[] arr, int l, int r) {
        if(r-l<=15){
            insertBase(arr,l,r);
            return ;
        }
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
//        arr[l+1,,,,lt]<v
        int lt = l;
//        arr[gt,,,r] > v
        int gt = r + 1;
//        arr[lt+1,,,,i) == v
        int i=l+1;
//        终止条件 i==gt
        while(i<gt){
            if(arr[i]<v){
               // arr[l+1,,,,lt]<v
                swap(arr,lt+1,i);
                lt++;
                i++;
            }else if(arr[i]>v){
//                arr[gt,,,r] > v
                swap(arr,i,gt-1);
                gt--;
            }else{
              i++;
            }


        }
        swap(arr,l,lt);
        quickSortInternal3(arr,l,lt-1);
        quickSortInternal3(arr,l,lt-1);
    }


    private static void swap(int[] arr, int i, int min) {
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;

    }

    public static void main(String[] args) throws Exception {
        int n = 1000000;
        int[] arr = SortHelper.generateRandomArray(n, 0,Integer.MAX_VALUE);
//        int[] arrCopy = SortHelper.arrCopy(arr);
        int[] arrCopy1 = SortHelper.arrCopy(arr);
        int[] arrCopy2 = SortHelper.arrCopy(arr);

//        SortHelper.testSort("selectionSort", arr);
//        SortHelper.testSort("selectionSortOP", arrCopy);
//        SortHelper.testSort("insertionSortBase", arrCopy1);
        SortHelper.testSort("quickSort", arrCopy2);
        SortHelper.testSort("mergeSortNonRecursion", arrCopy1);


    }


}
